﻿#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERORR 0

typedef int Status;
typedef int SElemType;
typedef struct SNode{
	SElemType data;
	struct SNode* next;
}StackNode, *LinkStack;


// 初始化 
Status InitStack(LinkStack& S);
// 入栈 
Status Push(LinkStack& S, SElemType pushElem);
// 遍历 
void TraverseStack(LinkStack S);
// 获取栈顶元素 
Status GetTop(LinkStack S, SElemType &topElem);
// 出栈 
Status Pop(LinkStack& S, SElemType &popElem);
// 判空 
bool StackEmpty(LinkStack S);
// 获取长度 
int StackLength(LinkStack S);

int main()
{
	LinkStack S;  // 创建栈（头指针）S
	if(InitStack(S) == OK){
		puts("链栈初始化成功！"); 
	}else{
		puts("链栈初始化失败！"); 
	} // 初始化 
	
	if(StackEmpty(S)){
		puts("当前链栈为空！"); 
	}else{
		puts("当前链栈不为空！"); 
	} 
	
	SElemType datas[5]={
		'A', 'B', 'C', 'D', 'E'
	};  // 定义入栈元素数组 
	
	SElemType *p;
	p = datas;
	int i = 0;
	SElemType pushElem;
	Status returnPush;
	for(i=0; i<5; i++){
		pushElem = *(p+i);
		returnPush = Push(S, pushElem);
		if(returnPush == OK){
			printf("向链栈入栈成功，入栈元素为：%C\n", pushElem);
		}else{
			printf("向链栈入栈失败！");
		}
	}

	TraverseStack(S);  // 遍历 
	
	int length = StackLength(S);
	printf("当前链栈长为：%d\n", length);

	
	SElemType topElem;
	Status returnGetTop; 
	returnGetTop = GetTop(S, topElem);  // 获取栈顶元素 
	if (returnGetTop == OK){
		printf("链栈的栈顶元素为：%c\n", topElem);
	}else{
		printf("当前链栈为空，栈顶元素获取失败！"); 
	} 

	SElemType popElem;  
	Status returnPop;
	returnPop = Pop(S, popElem);  // 出栈
	if (returnPop == OK)
		printf("从链栈中出栈成功，出栈元素为：%c\n", popElem);
	else{
		printf("从链栈中出栈失败！\n");
	} 

	TraverseStack(S);
	
	if(StackEmpty(S)){
		puts("当前链栈为空！"); 
	}else{
		puts("当前链栈不为空！！");  
	} 
	
	return 0;
}

// 初始化 
Status InitStack(LinkStack& S){
	S = NULL;  // 因为链栈是一个没有头节点的单链表，所以初始化只需将S置为空。
	return OK;
}

// 入栈 
Status Push(LinkStack &S, SElemType pushElem){
	LinkStack pushNode = new StackNode;  // 新节点分配空间
	pushNode->data = pushElem;  // 元素入栈
	pushNode->next = S;  // 新节点指针域为S，因链栈没有头节点，S装的是首元节点的地址
	S = pushNode;  // S指向新节点；因链栈的栈顶为第一节点；所以是一个逆序的单链表
	return OK;
}

// 遍历 
void TraverseStack(LinkStack S){
	LinkStack p = S;
	printf("当前链栈中的元素为："); 
	while (p){
		printf("%c", p->data);
		p = p->next;
	}
	printf("\n");
}

// 获取栈顶元素 
Status GetTop(LinkStack S, SElemType& topElem){
	if (S == NULL) // 判断栈是否为空 
	{
		printf("空栈没有栈顶\n");
		return ERORR;
	}
	topElem = S->data;  // 因链栈栈顶是第一个节点，则栈顶元素值为第一节点的值
	return OK;
}

// 出栈 
Status Pop(LinkStack &S, SElemType &popElem){
	LinkStack p;
	if (S == NULL){
		return ERORR;
	}
	p = S;
	popElem = p->data;  // 出栈的值 
	S = S->next;  // S指针后移 
	free(p);  // 释放出栈节点的空间
	return OK;
}

// 判空
bool StackEmpty(LinkStack S){
	if (S == NULL)
		return true;
	return false;
}

// 获取栈长 
int StackLength(LinkStack S){
	LinkStack p;
	int length = 0;
	p = S;
	while (p)
	{
		length++;
		p = p->next;
	}
	return length;
}

